package LinkedListAndArray;

public class SingleLinkedList_VirtualHead<E> extends AbstractList<E> {
	/**
	 * 虚拟头节点
	 */
	private Node<E> first;

	public SingleLinkedList_VirtualHead() {
		first = new Node<E>(null, null);
	}

	/**
	 * 链表节点 lianglibao 2019/5/23 3:41 PM
	 */
	private static class Node<E> {
		E element;
		Node<E> next;

		public Node(E element, Node<E> next) {
			this.element = element;
			this.next = next;
		}
	}

	/**
	 * 获取index位置节点 lianglibao 2019/5/23 4:03 PM
	 */
	private Node<E> node(int index) {
		rangeCheck(index);

		Node<E> node = first.next;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}

	@Override
	public void clear() {
		first.element = null;
		first.next = null;
		size = 0;
	}

	@Override
	public void add(int index, E element) {
		rangeCheckForAdd(index);

		Node<E> prev = (index == 0) ? first : node(index - 1);
		System.out.println("prev:" + prev.element + "," + "now:" + element);
		prev.next = new Node<E>(element, prev.next);
		size++;
	}

	@Override
	public int indexOf(E element) {
		if (element == null) {
			Node<E> node = first.next;
			for (int i = 0; i < size; i++) {
				if (node.element == null)
					return i;
				node = node.next;
			}
		} else {
			Node<E> node = first.next;
			for (int i = 0; i < size; i++) {
				if (element.equals(node.element))
					return i;
				node = node.next;
			}
		}
		return ELEMENT_NOT_FOUND;
	}

	@Override
	public E set(int index, E element) {
		rangeCheck(index);
		Node<E> node = node(index);
		E oldElement = node.element;
		node.element = element;
		return oldElement;
	}

	@Override
	public E get(int index) {
		rangeCheck(index);
		return (E) node(index).element;
	}

	@Override
	public E remove(int index) {
		rangeCheck(index);

		Node<E> prev = (index == 0) ? first : node(index - 1);
		Node<E> node = prev.next;
		prev.next = node.next;
		size--;
		return node.element;
	}

	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		Node<E> node = first.next;
		if (node != null) {
			sb.append("first" + "_" + node.element);
		} else {
			sb.append("first->null");
		}

		for (int i = 0; i < size; i++) {
			node = node.next;
			if (node != null) {
				sb.append("->" + node.element);
			} else {
				sb.append("->null");
			}
		}
		return sb.toString();
	}

}
